class Solution {
public:
    /*
    f[i]表示到i位置时乘积为正数的最长子数组的长度
    分为3种情况：
        1. f[i]的长度为1，又分两种情况
            a. nums[i]为正数，此时f[i] = 1
            b. nums[i]为负数，此时f[i] = 0
        2. f[i]的长度不为1，分两种情况
            a. nums[i]为正数，因为[正数 * 正数 = 正数]，此时f[i] = f[i - 1] + 1
            b. nums[i]为负数，因为[负数 * 负数 = 负数]，需要另一个dp表g[i]存储到i位置乘积为负数的最长子数组长度
                A.如果g[i - 1] = 0，凑不出负负得正，故f[i] = 0
                B.否则，f[i] = g[i - 1] + 1
        3. 如果nums[i] = 0，0乘以任何数都为0，故f[i] = 0
    */
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        auto g(f);

        int ret = 0;
        for (int i = 1; i < n + 1; ++i)
        {
            if (nums[i - 1] == 0)
            {
                f[i] = 0;
                g[i] = 0;
            }
            else
            {
                if (nums[i - 1] > 0)
                {
                    f[i] = f[i - 1] + 1;
                    g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                }
                else
                {
                    f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                    g[i] = f[i - 1] + 1;
                }

                ret = max(ret, f[i]);
            }
        }
        return ret;
    }   
};